package com.lwx.chapter8;

public class MaxHeap<E extends Comparable<E>> {
    //数组里存放的是最大堆的层序遍历
    private Array<E> data;
    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }
    public MaxHeap(){
        data = new Array<>();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    public int size(){
        return data.getSize();
    }

    //索引下标为index的父节点的索引下标，从数组的0开始放元素
    private int parent(int index){
        if(index == 0){
            throw new IllegalArgumentException("Index is illegal. ");
        }
        return (index -1) / 2;
    }

    private int leftChild(int index){
        return 2 * index + 1;
    }

    private int rightChild(int index){
        return 2 * index + 2;
    }

    //向堆中添加元素，实际上是整个数组的元素上浮的过程
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() -1);
    }

    //index所在的树进行上浮

    /**
     *
     * @param k 希望上浮的元素的下标
     */
    private void siftUp(int k){
        //当不是最上面的元素&&父节点的元素小于当前节点，进行父节点和当前节点交换
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k))<0){
                data.swap(k,parent(k));
                k = parent(k);
        }
    }

    public E findMax(){
        if(data.getSize() == 0){
            throw new IllegalArgumentException("MaxHeap is Empay.FindMax failed!");
        }
        return data.get(0);
    }
    public E extractMax(){
        E ret = findMax();
        data.swap(0, data.getSize() -1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    /**
     *
     * @param k 从下标为k进行下沉
     */
    private void siftDown(int k){
        //如果有左孩子
        while(leftChild(k) < data.getSize()){
            int j = leftChild(k);
            //如果有右孩子&&右孩子为较大的值
            if(j + 1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0){
                //j为右孩子的索引
                j ++;
            }
            //data[j]现在存储的是左右孩子中较大值
            if(data.get(k).compareTo(data.get(j)) > 0){
                break;
            }
            data.swap(k , j);
            k = j;
        }
        return;
    }

    /**
     * 取出最大值，并替换为e。将最大值的位置填入元素e,然后进行siftDown，log(n)
     * @param e
     * @return 最大值
     */
    public E replace(E e){
        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }

    //任意元素改为堆，每个逐渐插入o(nlogn),调用add;使用下面这个方法，o(n)
    //1.确定堆的最后一个非叶子节点，一次向前进行siftDown
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        //最后一个非叶子节点
        int lastParent = parent(data.getSize()-1);
        for (int i = lastParent; i >= 0 ; i--) {
            siftDown(i);
        }
    }

    @Override
    public String toString() {
        return "MaxHeap{" +
                "data=" + data +
                '}';
    }
}
